/*
leetcode 54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

 

示例 1：


输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：


输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
*/
#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        
        if (matrix.empty()) return result;
        
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        
        while (top <= bottom && left <= right) {
            // 从左到右沿着最上面一行遍历
            for (int i = left; i <= right; ++i) {
                result.push_back(matrix[top][i]);
            }
            top++;  // 将顶部边界向下移动
            
            // 从上到下沿着最右列遍历。
            for (int i = top; i <= bottom; ++i) {
                result.push_back(matrix[i][right]);
            }
            right--;  //将右边界向左移动
            
            if (top <= bottom) {
                //从右向左沿着底部一行遍历
                for (int i = right; i >= left; --i) {
                    result.push_back(matrix[bottom][i]);
                }
                bottom--;  //将底部边界向上移动
            }
            
            if (left <= right) {
                //从底向上沿着最左列遍历
                for (int i = bottom; i >= top; --i) {
                    result.push_back(matrix[i][left]);
                }
                left++;  //将左边界向右移动
            }
        }
        
        return result;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> matrix = {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }
    };
    
    vector<int> result = solution.spiralOrder(matrix);
    
    // 输出结果
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

/*
假设输入矩阵为：

[ [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

初始状态：
top = 0, bottom = 2, left = 0, right = 2
result = []（最终结果）

第一步：从左到右遍历上边界
我们首先遍历矩阵的上边界，从左到右：
遍历 matrix[0][0] = 1, matrix[0][1] = 2, matrix[0][2] = 3，把它们添加到 result 中。
更新 result：[1, 2, 3]
增加 top，使 top = 1。
当前状态：
result = [1, 2, 3]
top = 1, bottom = 2, left = 0, right = 2

第二步：从上到下遍历右边界
接下来遍历右边界，从上到下：
遍历 matrix[1][2] = 6，matrix[2][2] = 9，把它们添加到 result 中。
更新 result：[1, 2, 3, 6, 9]
减少 right，使 right = 1。
当前状态：
result = [1, 2, 3, 6, 9]
top = 1, bottom = 2, left = 0, right = 1

第三步：从右到左遍历下边界
接下来遍历下边界，从右到左：
遍历 matrix[2][1] = 8, matrix[2][0] = 7，把它们添加到 result 中。
更新 result：[1, 2, 3, 6, 9, 8, 7]
减少 bottom，使 bottom = 1。
当前状态：
result = [1, 2, 3, 6, 9, 8, 7]
top = 1, bottom = 1, left = 0, right = 1

第四步：从下到上遍历左边界
接下来遍历左边界，从下到上：
遍历 matrix[1][0] = 4，把它添加到 result 中。
更新 result：[1, 2, 3, 6, 9, 8, 7, 4]
增加 left，使 left = 1。
当前状态：
result = [1, 2, 3, 6, 9, 8, 7, 4]
top = 1, bottom = 1, left = 1, right = 1

第五步：从左到右遍历上边界（再次）
接下来遍历上边界，从左到右（当前上边界就是 matrix[1][1]）：
遍历 matrix[1][1] = 5，把它添加到 result 中。
更新 result：[1, 2, 3, 6, 9, 8, 7, 4, 5]
增加 top，使 top = 2。
当前状态：
result = [1, 2, 3, 6, 9, 8, 7, 4, 5]
top = 2, bottom = 1, left = 1, right = 1

终止条件
此时 top > bottom，left > right，我们退出循环。
最终结果为：
[1, 2, 3, 6, 9, 8, 7, 4, 5]
 */